import heapq


class Solution:
    def countRestrictedPaths(self, n: int, edges: list) -> int:
        def func(adj, u, distances, visited, memo):
            if u == n:
                return 1
            if u in memo:
                return memo[u]
            if u in visited:
                return 0
            visited.add(u)
            res = 0
            for v, _ in adj[u]:
                if distances[v] >= distances[u]:
                    continue
                res += func(adj, v, distances, visited, memo)
            memo[u] = res
            return res % (10**9 + 7)

        adj = [[] for _ in range(n + 1)]
        for edge in edges:
            adj[edge[0]] += [(edge[1], edge[2])]
            adj[edge[1]] += [(edge[0], edge[2])]
        queue = [(0, n)]
        visited = set()
        distances = [0 for _ in range(n + 1)]
        while queue:
            nd, cur = heapq.heappop(queue)
            if cur in visited:
                continue
            visited.add(cur)
            distances[cur] = nd
            for nei, d in adj[cur]:
                heapq.heappush(queue, (d + nd, nei))

        return func(adj, 1, distances, set(), {})
